package com.sicheng.lc.周赛.分类.栈;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/6/29 9:45
 */
public class 替换数组中的非互质数 {
    //https://leetcode.cn/problems/replace-non-coprime-numbers-in-array/
    public List<Integer> replaceNonCoprimes(int[] nums) {
        //避免不断扩容 底层产生arraycopy
        ArrayList<Integer> stack = new ArrayList<>(10000);
        for (int num : nums) {
            int lcm = num;
            if (!stack.isEmpty() && num != 1 && num == stack.get(stack.size() - 1))
                continue;
            while (!stack.isEmpty() && gcd(stack.get(stack.size() - 1), lcm) > 1) {
                int top = stack.remove(stack.size() - 1);
                lcm = lcm(top, lcm);
            }
            stack.add(lcm);
        }
        return stack;
    }

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    private int lcm(int a, int b) {
        return (int) ((long) a * b / gcd(a, b));
    }

    public static void main(String[] args) {
        替换数组中的非互质数 s = new 替换数组中的非互质数();
        int[] nums = {
                13981, 11, 25, 10535, 19565, 19379, 19379, 19379, 19379, 19379,
                19379, 19379, 19379, 19379, 19379, 19379, 19379, 19379, 19379,
                19379, 19379, 19379, 19379, 19379, 19379, 19379, 19379, 19379, 19379, 19379, 19379,
                19379, 72977, 72977, 72977, 72977, 72977, 72977, 72977, 72977, 72977, 72977, 72977,
                72977, 72977, 72977, 72977, 72977, 72977, 72977, 72977, 72977, 72977, 2269, 2269, 2269,
                2269, 2269, 2269, 2269, 2269, 2269, 2269, 2269, 2269, 2269, 2269, 2269, 2269, 33533, 155,
                145, 4205, 4495, 725, 29, 29, 145, 25, 725, 5, 145, 5, 5, 155, 155, 5, 5, 5, 1121, 1121, 59,
                59, 59, 361, 19, 19, 19, 1121, 19, 361, 1121, 1121, 361, 361, 19, 19, 80246, 4, 2, 2, 2, 37717,
                37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717,
                37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717,
                37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717,
                37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717,
                37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717,
                37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717,
                37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717,
                37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717,
                37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717,
                37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717,
                37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717,
                37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717,
                37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717,
                37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717,
                37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717,
                37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717,
                37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717,
                37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717,
                37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717,
                37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717,
                37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717,
                37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717,
                37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717,
                37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717,
                37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717,
                37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717, 37717,
                37717, 37717, 37717, 4042, 86, 2, 172, 86, 4042, 4042, 172, 3698, 172, 2, 172, 86, 2, 172, 43, 1849, 3698, 13, 121, 143, 143, 11, 11, 11, 143, 143, 93, 31, 31, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797, 44797};
        System.out.println(s.replaceNonCoprimes(nums));
    }
}
